package leetcode.code0395;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int longestSubstring(String s, int k) {
		char[] cs = s.toCharArray();
		int l = 1, r = 26;
		int ans = 0;
		while (l <= r) {
			int mid = ((r - l) >> 1) + l;
			int cur = has(cs, mid, k);
			if (cur > 0 && cur >= ans) {
				ans = cur;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return ans;
	}

	private int has(char[] cs, int mid, int k) {
		int[] dics = new int[26];
		int kind = 0;
		int max = 0;
		for (int r = 0, l = 0; r < cs.length; r++) {
			int cur = cs[r] - 'a';
			if (dics[cur] == 0) {
				kind++;
			}
			dics[cur]++;
			if (kind > mid) {
				int L = -1;
				do {
					L = cs[l++] - 'a';
					dics[L]--;
				} while (dics[L] != 0 && l < r);
				kind--;
			}
			if (kind == mid) {
				int min = Integer.MAX_VALUE;
				for (int num : dics) {
					if (num != 0) {
						min = Math.min(min, num);
					}
				}
				if (min >= k) {
					max = Math.max(max, r - l + 1);
				}
			}
		}
		return max;
	}

	@Override
	public void debug4() {
		HelpDebug.compare(6, this.longestSubstring("aaabbb", 3));
		HelpDebug.compare(3, this.longestSubstring("aaabb", 3));
		HelpDebug.compare(5, this.longestSubstring("ababbc", 2));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
